/*
 * @lc app=leetcode.cn id=404 lang=cpp
 *
 * [404] 左叶子之和
 *
 * https://leetcode-cn.com/problems/sum-of-left-leaves/description/
 *
 * algorithms
 * Easy (60.09%)
 * Likes:    431
 * Dislikes: 0
 * Total Accepted:    141.3K
 * Total Submissions: 234.8K
 * Testcase Example:  '[3,9,20,null,null,15,7]'
 *
 * 给定二叉树的根节点 root ，返回所有左叶子之和。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 
 * 
 * 输入: root = [3,9,20,null,null,15,7] 
 * 输出: 24 
 * 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入: root = [1]
 * 输出: 0
 * 
 * 
 * 
 * 
 * 提示:
 * 
 * 
 * 节点数在 [1, 1000] 范围内
 * -1000 <= Node.val <= 1000
 * 
 * 
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    // //递归遍历！！！！！
    // int sumOfLeftLeaves(TreeNode* root) {
    //     if(root == NULL) return 0;

    //     //操作证明：
    //     //前序遍历是可以的
    //     int validVal = 0;
    //     if(root->left && !root->left->left && !root->left->right) {
    //         validVal = root->left->val;
    //     }

    //     int leftValue = sumOfLeftLeaves(root->left);
    //     int rightValue = sumOfLeftLeaves(root->right);

    //     // //操作证明：
    //     // //后序遍历也是可以的
    //     // int validVal = 0;
    //     // if(root->left && !root->left->left && !root->left->right) {
    //     //     validVal = root->left->val;
    //     // }

    //     int sum = validVal + leftValue + rightValue;

    //     return sum;
        
    // }


    //迭代遍历-深度优先遍历-统一遍历
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        if(cur == NULL) return 0;
        st.push(cur);
        int sum = 0;

        while(!st.empty()) {
            cur = st.top();

            if(cur != NULL) {
                st.pop();
                if (cur->right) st.push(cur->right);
                if (cur->left) st.push(cur->left);
                
                st.push(cur);
                st.push(NULL);
            } else {
                st.pop();
                cur = st.top();
                st.pop();
                if(cur->left && !cur->left->left && !cur->left->right) {
                    sum += cur->left->val;
                }
            }

        }
        return sum;
    }


};
// @lc code=end

